package 嵌套类问题的递归解题套路;

import java.util.ArrayList;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 含有嵌套的表达式求值
// 测试链接 : https://leetcode.cn/problems/basic-calculator-iii/
public class Code01_BasicCalculatorIII {

    public static int calculate(String str) {
        where = 0;
        return f(str.toCharArray(), 0);
    }

    // 记录递归返回时的右括号的位置，以便后续的进行
    public static int where;

    // s[i....]开始计算，遇到字符串终止 或者 遇到)停止
    // 返回 : 自己负责的这一段，计算的结果
    // 返回之间，更新全局变量where，为了上游函数知道从哪继续！
    public static int f(char[] s, int i){
        int cur = 0;
        // 数字栈，符号栈，用数组实现
        ArrayList<Integer> numbers = new ArrayList<>();
        ArrayList<Character> ops = new ArrayList<>();
        while (i < s.length && s[i] != ')'){
            if(s[i] >= '0' && s[i] <= '9'){
                cur = cur * 10 + s[i++] - '0';
            }else if(s[i] != '('){
                // 遇到了运算符 + - * /，进行更新
                push(numbers, ops, cur, s[i++]);
                cur = 0;
            }else {
                // i (.....)
                // 遇到了左括号！遇左括号就递归，遇到右括号，就返回
                // 从左括号的下一个位置开始递归
                cur = f(s, i+1);
                i = where+1;
            }
        }
        // 遇到')' 或者字符串，将前一个数加入到栈中，后面跟 '+'
        push(numbers, ops, cur, '+');
        // 全局变量，记录右括号的位置
        where = i;
        // 返回当前递归，栈中的计算结果
        return compute(numbers, ops);
    }

    public static void push(ArrayList<Integer> nums, ArrayList<Character> ops, int cur, char op){
        int n = nums.size();
        // 如果是加入第一个数字或者加入前 符号栈的栈顶字符不是 '*' 或者 '/' 直接入栈
        // 否则先将 数字栈和符号栈的栈顶元素弹出，与要入栈的值cur进行计算后再将结果入栈
        if(n == 0 || ops.get(n-1) == '+' || ops.get(n-1) == '-'){
            nums.add(cur);
            ops.add(op);
        }else {
            int topNum = nums.get(n-1);
            char topChar = ops.get(n-1);
            if(topChar == '*'){
                nums.set(n-1, topNum * cur);
            }else {
                nums.set(n-1, topNum / cur);
            }
            ops.set(n-1, op);
        }
    }

    // 栈中只剩 '+'或者'-' 号，进行计算
    public static int compute(ArrayList<Integer> nums, ArrayList<Character> ops){
        int ans = nums.get(0);
        int n = nums.size();
        for(int i = 1; i < n; i++){
            ans += ops.get(i-1) == '+' ? nums.get(i) : -nums.get(i);
        }
        return ans;
    }
}
